// 左右双指针
// 利用数组的单调性，配合左右双指针，遍历一遍数组，完成题目要求
// 可以从题目的暴力解法入手，双指针的解法通常可以少遍历一遍数组，将时间复杂度降低O(N)

// 例题 6：
//购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。
//
//        示例 1：
//
//        输入：price = [3, 9, 12, 15], target = 18
//        输出：[3,15] 或者 [15,3]
//        示例 2：
//
//        输入：price = [8, 21, 27, 34, 52, 66], target = 61
//        输出：[27,34] 或者 [34,27]
//
//
//        提示：
//
//        1 <= price.length <= 10^5
//        1 <= price[i] <= 10^6
//        1 <= target <= 2*10^6

// 解题思路：
//  首先 price 是一个有序数组，本身具备单调递增的特性
//  其次设定 left 表示最小价格的下标，right 表示最大价格的下标
//  通过判断 price[left] + price[right] 与 target 的大小关系，决定 left++ 或者 right--
public class TwoSum {
    public int[] twoSum(int[] price, int target) {
        int n = price.length;
        int left = 0;
        int right = n - 1;
        int[] ret = new int[2];
        while(left < right){
            int sum = price[left] + price[right];
            if(sum < target) left++;
            else if(sum > target) right--;
            else {
                ret[0] = price[left];
                ret[1] = price[right];
                break;
            }
        }
        return  ret;
    }
}
